// 题目描述
// 316. 去除重复字母
// 提示
// 中等
// 992
// 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
//   示例 1：
// 输入：s = "bcabc"
// 输出："abc"
// 示例 2：
// 输入：s = "cbacdcbc"
// 输出："acdb"
//   提示：
// 1 <= s.length <= 104
// s 由小写英文字母组成
//   注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同
// 通过次数
// 125K
// 提交次数
// 257.8K
// 通过率
// 48.5%
// https://leetcode.cn/problems/remove-duplicate-letters

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function (s) {
  const sLen = s.length

  // 记录字符最后出现的位置
  const lastIdx = {}
  for (let i = 0; i < sLen; i++) {
    lastIdx[s[i]] = i
  }

  // 利用单调栈性质
  const sk = [], peek = () => sk[sk.length - 1]
  const visited = new Set()
  for (let i = 0; i < sLen; i++) {
    const ch = s[i]
    if (visited.has(ch)) {
      continue
    }

    while (sk.length && peek() > ch && lastIdx[peek()] > i) {
      visited.delete(sk.pop())
    }

    sk.push(ch)
    visited.add(ch)
  }

  return sk.join('')
}

console.log(
  removeDuplicateLetters('bcabc')
)
